package LinkTest;

import java.util.HashSet;
import java.util.Set;

//判链表是否有环两种方法
//找到链表环的入口点
public class CycleLink {
    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
  //前后指针法
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode prev=head;
        ListNode s=head;
        while(s!=null&&s.next!=null){
            prev=prev.next;
            s=s.next.next;
            if(prev==s){
                return true;
            }
        }
        return false;
    }
    //存入set集合判是否重复，若有重复表示有环
    public boolean hasCycle1(ListNode head){
        if(head==null){
            return false;
        }
        ListNode cur=head;
        Set<ListNode> set=new HashSet<>();//Set接口
        while(cur!=null){
            if(set.contains(cur)){
                return true;
            }
            set.add(cur);
            cur=cur.next;
        }
        return false;
    }
    //找到链表环的入点第一种方法前后指针法
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead==null){
            return null;
        }
        ListNode pre=pHead;
        ListNode s=pHead;
        while(s!=null&&s.next!=null){
            pre=pre.next;
            s=s.next.next;

            if(pre==s){

                while(pHead!=pre){
                    pre=pre.next;
                    pHead=pHead.next;
                }
                return pre;
            }
        }
        return null;

    }
    //找到链表环的入口节点的第二种方法存入set集合昭重复的点
    public ListNode EntryNodeOfLoop2(ListNode pHead) {
        if(pHead==null){
            return null;
        }
        Set <ListNode> set=new HashSet<>();
        ListNode cur=pHead;
        while(cur!=null){
            if(set.contains(cur)){
                return cur;
            }
            set.add(cur);
            cur=cur.next;
        }
        return null;
    }
}
